package com.lc.lc3335;

import java.util.*;
public class Main {

}

class Solution {
	long[][] mp;
	int mod = (int)(1e9 + 7);
    public int lengthAfterTransformations(String s, int t) {
    	long ans = 0;
    	mp = new long[27][t + 1];
    	
    	for (int i = 0; i < 27; i ++) {
    		Arrays.fill(mp[i], -1);
    	}
    	
    	for (int i = 0; i < s.length(); i ++) {
    		ans += solve(s.charAt(i), t) % mod;
    	}
    	return (int)(ans % mod);
    }
    
    long solve(char c, int t) {
    	if (mp[c - 'a'][t] != -1) {
    		return mp[c - 'a'][t];
    	}
    	if (c + t <= 'z' ) {
    		return 1;
    	} else {
    		int tt = 'z' - c + 1;
    		long ans = solve('a', t - tt) % mod + solve('b', t - tt) % mod;
    		mp[c - 'a'][t] = ans % mod;
    		return ans;
    	}
    }
}
